#ifndef CS240_BST_H
#define CS240_BST_H

#include <string>
#include <stdlib.h>
#include <iostream>
#include <stdio.h>
#include "LinkedList.h"

using namespace std;

template <typename S> class BST;

//!BSTNode implements a binary search tree node
template <typename T>
class BSTNode {
		friend class BST<T>;   //!< BST can access private members of BSTNode
		
	public:
	
		//!  Constructor
		BSTNode(const T & v) :
		  value(v), left(NULL), right(NULL){
		}
		
		//! Copy Constructor
		BSTNode(const BSTNode<T> & other) :
		  value(other.value),left(other.left),right(other.right){
		}
		
		~BSTNode(){
			
		}
		
		BSTNode<T> * FullCopy(){
			BSTNode<T> *temp= new BSTNode<T>(value);
			if(left!=NULL)
				temp->left=left->FullCopy();
			if(right!=NULL)
				temp->right=right->FullCopy();


			return temp;
		}

		void FullDelete(){
			if(right!=NULL){
				right->FullDelete();
				delete right;
				right = NULL;
			}
			if(left!=NULL){
				left->FullDelete();
				delete left;
				left = NULL;
			}

		}
	
		//!  Read-only public methods for use by clients of the BST class
		const T & GetValue() const{
		  return value;
		}
	
		
	
		BSTNode<T> * GetLeft()const{
		  return left;
		}
	
	
		BSTNode<T> * GetRight()const{
		  return right;
		}
		
		//! Assignment operator 
		BSTNode<T> & operator=(const BSTNode<T> & other){
			if(this!=&other){
				value=other.value;
				left=other.left;
				right=other.right;
			}
			
			return *this;
		}

		void print(){
			cout <<value <<endl;
		}
	
	private:
		T value;  //!< value stored in the node
		BSTNode<T> * left;     //!< pointer to the node's left child
		BSTNode<T> * right;    //!< pointer to the node's right child
};


//!  BST implements a binary search tree
template <typename L>
class BST {
	
	public:
		BST(){
			root=NULL;
			size=0;
		}


		BST(const BST<L> & other){
			if (other.root==NULL)
				root=NULL;
			else
				this->root = other.root->FullCopy();
			size=other.GetSize();
		}


		~BST(){
			if (root!=NULL){
				root->FullDelete();
				delete root;
				root=NULL;
			}
		}


		BST<L>& operator =(const BST<L> & other){
			if (this != &other){
				if (root!=NULL){
					root->FullDelete();
					delete root;
					root=NULL;
				}
				if (other.root==NULL)
					root=NULL;
				else
					this->root = other.root->FullCopy();
				size=other.GetSize();
			}
			return *this;
		}



		L * GetRoot()const{
			return &(root->value);
		}



		bool IsEmpty() const{
			if (size==0)
				return true;
			return false;
		}



		void Clear(){
			root->FullDelete();
			delete root;
			root=NULL;
			size=0;
		}



		int GetSize() const{
			return size;
		}

		BSTNode<L> * Insert(L & v){
			if (root==NULL){
				size++;
				return root = new BSTNode<L>(v);
			}
			else{
				if (root->value.compare(v)==0)
					return NULL;
				return Insert(*root,v);
			}
		}


		bool contains( L &v){
			if (Find(v)!=NULL)
				return true;
			return false;
		}


		L* FindItem(L & v) const{
			return &(Find(v)->value);
		}

		BSTNode<L> * Find(L & v) const{
			if (root==NULL)
				return NULL;
			return Find(*root,v);
		}




		void printTree(){
			if (root!=NULL)
				printTree(*root);
			else
				cout<< "empty" << endl;
		}

		LinkedList<L>* toLinkedList(){
			LinkedList<L> *list = new LinkedList<L>();
			toLinkedList(*root,*list);

			return list;
		}


	
	
	private:
		BSTNode<L> *root;
		int size;
		
		BSTNode<L> * Insert(BSTNode<L> & cur, L & v){
						if (cur.value.compare(v)==0)
								return NULL;

						if (v.compare(cur.value)>=0){
							if (cur.right==NULL){
								size++;
								return cur.right=new BSTNode<L>(v);
							}else
								return Insert(*(cur.right),v);
						}
						else{
							if (cur.left==NULL){
								size++;
								return cur.left=new BSTNode<L>(v);
							}
							else
								return Insert(*(cur.left),v);
						}
				}
		
		BSTNode<L> * Find(BSTNode<L> & cur,L & v) const{
					if (v.compare(cur.value)==0)
						return &cur;
					if (v.compare(cur.value)>=0 && cur.right!=NULL){
						return Find(*(cur.right),v);
					}
					if (v.compare(cur.value)<0 && cur.left!=NULL){
						return Find(*(cur.left),v);
					}
					return NULL;
				}

		void printTree(BSTNode<L> & cur){
					if (cur.right!=NULL)
						printTree(*(cur.right));
					cout<< cur.value << endl;
					if (cur.left!=NULL)
						printTree(*(cur.left));

				}

		void toLinkedList(BSTNode<L> &cur,LinkedList<L> &list){
			if (cur.right!=NULL)
				toLinkedList(*(cur.right),list);
			list.Insert(cur.value);
			if (cur.left!=NULL)
				toLinkedList(*(cur.left),list);
		}
};



#endif
